package leetcode;

/**
 * http://www.leetcode.com/onlinejudge
 * 
 * Add Binary
 * 
 * Given two binary strings, return their sum (also a binary string).
 * 
 * For example, a = "11" b = "1" Return "100".
 * 
 * @author yunzhang
 * 
 */
public class AddBinary {
	/**
	 * Converts the strings to char[] then each to int, apply the bitwise add.
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public String addBinary(String a, String b) {
		if (a == null || b == null || a.length() == 0 || b.length() == 0)
			return null;

		char[] ca = a.toCharArray();
		char[] cb = b.toCharArray();

		int carrier = 0;
		int pa = a.length() - 1;
		int pb = b.length() - 1;

		StringBuilder sb = new StringBuilder();

		while (pa >= 0 || pb >= 0) {
			int da = (pa >= 0) ? Character.getNumericValue(ca[pa]) : 0;
			int db = (pb >= 0) ? Character.getNumericValue(cb[pb]) : 0;

			sb.insert(0, da ^ db ^ carrier);

			carrier = (da + db + carrier > 1) ? 1 : 0;

			--pa;
			--pb;
		}

		if (carrier == 1)
			sb.insert(0, 1);

		return sb.toString();
	}
}
